#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<vector<int>> res;
    void dfs(map<int, bool>& hash, vector<int>& rs)
    {
        bool flag = true;
        for (auto& pair : hash)
        {
            if (pair.second)
            {
                flag = false;
                rs.push_back(pair.first);
                pair.second = false;
                dfs(hash, rs);
                pair.second = true;
                rs.pop_back();
            }
        }
        if (flag)
        {
            res.push_back(rs);;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> tmp;
        map<int, bool> hash;
        for (auto& e : nums) hash[e] = true;
        dfs(hash, tmp);
        return res;
    }
};